package acwing.code1222;

public class Solution {

	public int find(String input) {
		char[] cs = input.toCharArray();
		int len = cs.length;
		Integer[][] dp = new Integer[len + 1][len + 1];
		return find(cs, 0, len - 1, dp);
	}

	private int find(char[] cs, int l, int r, Integer[][] dp) {
		if (l == r || l == cs.length || r == -1 || (r - l == 1 && cs[l] == cs[r])) {
			return 0;
		}
		if (dp[l][r] != null) {
			return dp[l][r];
		}
		char L = cs[l];
		char R = cs[r];
		int ans1 = Integer.MAX_VALUE;
		if (L == R) {
			ans1 = this.find(cs, l + 1, r - 1, dp);
		}
		int ans2 = this.find(cs, l + 1, r, dp) + 1;
		int ans3 = this.find(cs, l, r - 1, dp) + 1;
		int ans = Math.min(ans2, Math.min(ans1, ans3));
		dp[l][r] = ans;
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		int ans = 0;
		ans = so.find("ABDCDCBABC");
		System.out.println(ans);
		ans = so.find("ABDCDDDCBACBABC");
		System.out.println(ans);
		ans = so.find("ACBCC");
		System.out.println(ans);

	}

}
